package go_leetcode

import "sort"

// 两层for循环
func countPairs(nums []int, target int) int {
	res := 0
	length := len(nums)
	for i := 0; i < length-1; i++ {
		for j := i + 1; j < length; j++ {
			if nums[i]+nums[j] < target {
				res++
			}
		}
	}
	return res
}

// 单层for循环 + 二分查找
func countPairs2(nums []int, target int) int {
	sort.Ints(nums)
	res := 0
	for i := 1; i < len(nums); i++ {
		res += sort.SearchInts(nums[0:i], target - nums[i])
	}
	return res
}